package org.example.myleet.p1475;

import java.util.Deque;
import java.util.LinkedList;

public class Solution {

    public int[] finalPrices(int[] prices) {
        Deque<Integer> stack = new LinkedList<>();
        int[] nextDiscount = new int[prices.length];
        for (int i = prices.length - 1; i >= 0; --i) {
            if (stack.isEmpty()) {
                stack.push(prices[i]);
                nextDiscount[i] = 0;
            } else {
                while (!stack.isEmpty() && prices[i] < stack.peek()) {
                    stack.pop();
                }
                if (stack.isEmpty()) {
                    nextDiscount[i] = 0;
                } else {
                    nextDiscount[i] = stack.peek();
                }
                stack.push(prices[i]);
            }
        }
        for (int i = 0; i < prices.length; ++i) {
            prices[i] -= nextDiscount[i];
        }
        return prices;
    }

//    public int[] finalPrices(int[] prices) {
//        for (int i = 0; i < prices.length; ++i) {
//            for (int j = i + 1; j < prices.length; ++j) {
//                if (prices[i] >= prices[j]) {
//                    prices[i] -= prices[j];
//                    break;
//                }
//            }
//        }
//        return prices;
//    }
}
